Mi manual de algoritmos/source_highlight/src/grafos/dijkstra.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2 \noindent
   3 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$iostream$>$}} \\
   4 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$vector$>$}} \\
   5 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$queue$>$}} \\
   6 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$map$>$}} \\
   7 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$cmath$>$}} \\
   8 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$sstream$>$}} \\
   9 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$functional$>$}} \\
  10 \mbox{} \\
  11 \mbox{}\textbf{\textcolor{Blue}{using}}\ \textbf{\textcolor{Blue}{namespace}}\ std\textcolor{BrickRed}{;} \\
  12 \mbox{} \\
  13 \mbox{}\textbf{\textcolor{Blue}{const}}\ \textcolor{ForestGreen}{double}\ infinity\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{1E20}\textcolor{BrickRed}{;} \\
  14 \mbox{} \\
  15 \mbox{}\textbf{\textcolor{Blue}{struct}}\ point\textcolor{Red}{\{} \\
  16 \mbox{}\ \ \textcolor{ForestGreen}{double}\ x\textcolor{BrickRed}{,}\ y\textcolor{BrickRed}{;} \\
  17 \mbox{}\ \ \textbf{\textcolor{Black}{point}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{double}\ X\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{double}\ Y\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ x\ \textcolor{BrickRed}{=}\ X\textcolor{BrickRed}{;}\ y\ \textcolor{BrickRed}{=}\ Y\textcolor{BrickRed}{;}\textcolor{Red}{\}} \\
  18 \mbox{}\textcolor{Red}{\}}\textcolor{BrickRed}{;} \\
  19 \mbox{} \\
  20 \mbox{}map\textcolor{BrickRed}{$<$}\ point\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{double}\ \textcolor{BrickRed}{$>$}\ dist\textcolor{BrickRed}{;} \\
  21 \mbox{} \\
  22 \mbox{}\textcolor{ForestGreen}{bool}\ \textbf{\textcolor{Blue}{operator}}\ \textcolor{BrickRed}{==(}\textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}a\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}b\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ \textbf{\textcolor{Blue}{return}}\ \textcolor{BrickRed}{(}a\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{==}\ b\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{\&\&}\ a\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{==}\ b\textcolor{BrickRed}{.}y\textcolor{BrickRed}{);}\textcolor{Red}{\}} \\
  23 \mbox{}\textcolor{ForestGreen}{bool}\ \textbf{\textcolor{Blue}{operator}}\ \textcolor{BrickRed}{!=(}\textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}a\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}b\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ \textbf{\textcolor{Blue}{return}}\ \textcolor{BrickRed}{!(}a\ \textcolor{BrickRed}{==}\ b\textcolor{BrickRed}{);}\textcolor{Red}{\}} \\
  24 \mbox{}\textcolor{ForestGreen}{bool}\ \textbf{\textcolor{Blue}{operator}}\ \textcolor{BrickRed}{$<$(}\textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}a\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}b\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ \textbf{\textcolor{Blue}{return}}\ \textcolor{BrickRed}{(}a\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{$<$}\ b\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{$|$$|$}\ \textcolor{BrickRed}{(}a\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{==}\ b\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{\&\&}\ a\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{$<$}\ b\textcolor{BrickRed}{.}y\textcolor{BrickRed}{));}\textcolor{Red}{\}} \\
  25 \mbox{}\textcolor{ForestGreen}{double}\ \textbf{\textcolor{Black}{distancia}}\textcolor{BrickRed}{(}point\ a\textcolor{BrickRed}{,}\ point\ b\textcolor{BrickRed}{)}\textcolor{Red}{\{}\textbf{\textcolor{Blue}{return}}\ \textbf{\textcolor{Black}{hypot}}\textcolor{BrickRed}{(}a\textcolor{BrickRed}{.}y\textcolor{BrickRed}{-}b\textcolor{BrickRed}{.}y\textcolor{BrickRed}{,}\ a\textcolor{BrickRed}{.}x\textcolor{BrickRed}{-}b\textcolor{BrickRed}{.}x\textcolor{BrickRed}{);}\textcolor{Red}{\}} \\
  26 \mbox{} \\
  27 \mbox{} \\
  28 \mbox{}\textbf{\textcolor{Blue}{struct}}\ heapCompare\ \textcolor{BrickRed}{:}\ \textbf{\textcolor{Blue}{public}}\ binary$\_$function\textcolor{BrickRed}{$<$}point\textcolor{BrickRed}{,}\ point\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{bool}\textcolor{BrickRed}{$>$} \\
  29 \mbox{}\textcolor{Red}{\{} \\
  30 \mbox{}\ \ \textcolor{ForestGreen}{bool}\ \textbf{\textcolor{Blue}{operator}}\textcolor{BrickRed}{()(}\textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}x\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}y\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{const}} \\
  31 \mbox{}\ \ \textcolor{Red}{\{}\ \textbf{\textcolor{Blue}{return}}\ dist\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{$>$}\ dist\textcolor{BrickRed}{[}y\textcolor{BrickRed}{];}\ \textcolor{Red}{\}} \\
  32 \mbox{}\textcolor{Red}{\}}\textcolor{BrickRed}{;} \\
  33 \mbox{} \\
  34 \mbox{} \\
  35 \mbox{}\textbf{\textcolor{Blue}{struct}}\ grafo\textcolor{Red}{\{} \\
  36 \mbox{}\ \ \textit{\textcolor{Brown}{//contiene\ todos\ los\ nodos\ sueltos}} \\
  37 \mbox{}\ \ vector\textcolor{BrickRed}{$<$}point\textcolor{BrickRed}{$>$}\ nodos\textcolor{BrickRed}{;} \\
  38 \mbox{}\ \ \textit{\textcolor{Brown}{//contiene\ un\ vector\ con\ todos\ los\ vecinos\ para\ el\ punto\ point}} \\
  39 \mbox{}\ \ map\textcolor{BrickRed}{$<$}\ point\textcolor{BrickRed}{,}\ vector\textcolor{BrickRed}{$<$}point\textcolor{BrickRed}{$>$}\ \textcolor{BrickRed}{$>$}\ vecinos\textcolor{BrickRed}{;} \\
  40 \mbox{} \\
  41 \mbox{}\ \ \textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{insert}}\textcolor{BrickRed}{(}point\ a\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  42 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}vecinos\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{count}}\textcolor{BrickRed}{(}a\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{==}\ \textcolor{Purple}{1}\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{return}}\textcolor{BrickRed}{;}\ \textit{\textcolor{Brown}{//Ya\ insertamos\ este\ nodo}} \\
  43 \mbox{}\ \ \ \ nodos\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{push$\_$back}}\textcolor{BrickRed}{(}a\textcolor{BrickRed}{);} \\
  44 \mbox{}\ \ \ \ vector\textcolor{BrickRed}{$<$}point\textcolor{BrickRed}{$>$}\ v\textcolor{BrickRed}{;} \\
  45 \mbox{}\ \ \ \ vecinos\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{insert}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{make$\_$pair}}\textcolor{BrickRed}{(}a\textcolor{BrickRed}{,}\ v\textcolor{BrickRed}{));} \\
  46 \mbox{}\ \ \textcolor{Red}{\}} \\
  47 \mbox{} \\
  48 \mbox{}\ \ \textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{make$\_$vecinos}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{double}\ maxPath\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  49 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}map\textcolor{BrickRed}{$<$}\ point\textcolor{BrickRed}{,}\ vector\textcolor{BrickRed}{$<$}point\textcolor{BrickRed}{$>$}\ \textcolor{BrickRed}{$>$::}iterator\ it\textcolor{BrickRed}{=}vecinos\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{begin}}\textcolor{BrickRed}{();}\ it\textcolor{BrickRed}{!=}vecinos\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{end}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}it\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  50 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Black}{distancia}}\textcolor{BrickRed}{((*}it\textcolor{BrickRed}{).}first\textcolor{BrickRed}{,}\ \textbf{\textcolor{Black}{point}}\textcolor{BrickRed}{(}\textcolor{Purple}{0.00}\textcolor{BrickRed}{,}\ \textcolor{Purple}{0.00}\textcolor{BrickRed}{))}\ \textcolor{BrickRed}{$>$}\ maxPath\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  51 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{continue}}\textcolor{BrickRed}{;} \\
  52 \mbox{}\ \ \ \ \ \ \textcolor{Red}{\}} \\
  53 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}map\textcolor{BrickRed}{$<$}\ point\textcolor{BrickRed}{,}\ vector\textcolor{BrickRed}{$<$}point\textcolor{BrickRed}{$>$}\ \textcolor{BrickRed}{$>$::}iterator\ jt\ \textcolor{BrickRed}{=}\ it\textcolor{BrickRed}{;}\ jt\textcolor{BrickRed}{!=}vecinos\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{end}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}jt\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  54 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{((*}it\textcolor{BrickRed}{).}first\ \textcolor{BrickRed}{!=}\ \textcolor{BrickRed}{(*}jt\textcolor{BrickRed}{).}first\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  55 \mbox{}\ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{((*}jt\textcolor{BrickRed}{).}first\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{-}\ \textcolor{BrickRed}{(*}it\textcolor{BrickRed}{).}first\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{$>$}\ \textcolor{Purple}{1.5}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  56 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{break}}\textcolor{BrickRed}{;} \\
  57 \mbox{}\ \ \ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  58 \mbox{}\ \ \ \ \ \ \ \ \ \ vector\textcolor{BrickRed}{$<$}point\textcolor{BrickRed}{$>$}\ adj\ \textcolor{BrickRed}{=}\ vecinos\textcolor{BrickRed}{[(*}it\textcolor{BrickRed}{).}first\textcolor{BrickRed}{];} \\
  59 \mbox{}\ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Black}{distancia}}\textcolor{BrickRed}{((*}jt\textcolor{BrickRed}{).}first\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{(*}it\textcolor{BrickRed}{).}first\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{$<$=}\ \textcolor{Purple}{1.5}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  60 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ vecinos\textcolor{BrickRed}{[(*}it\textcolor{BrickRed}{).}first\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{push$\_$back}}\textcolor{BrickRed}{((*}jt\textcolor{BrickRed}{).}first\textcolor{BrickRed}{);} \\
  61 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ vecinos\textcolor{BrickRed}{[(*}jt\textcolor{BrickRed}{).}first\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{push$\_$back}}\textcolor{BrickRed}{((*}it\textcolor{BrickRed}{).}first\textcolor{BrickRed}{);} \\
  62 \mbox{}\ \ \ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  63 \mbox{}\ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  64 \mbox{}\ \ \ \ \ \ \textcolor{Red}{\}} \\
  65 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  66 \mbox{}\ \ \textcolor{Red}{\}} \\
  67 \mbox{}\ \  \\
  68 \mbox{}\ \ \textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{initialize}}\textcolor{BrickRed}{()}\textcolor{Red}{\{} \\
  69 \mbox{}\ \ \ \ dist\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{clear}}\textcolor{BrickRed}{();} \\
  70 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}nodos\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  71 \mbox{}\ \ \ \ \ \ dist\textcolor{BrickRed}{[}nodos\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]]}\ \textcolor{BrickRed}{=}\ infinity\textcolor{BrickRed}{;} \\
  72 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}nodos\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}x\ \textcolor{BrickRed}{==}\ \textcolor{Purple}{0.00}\ \textcolor{BrickRed}{\&\&}\ nodos\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}y\ \textcolor{BrickRed}{==}\ \textcolor{Purple}{0.00}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  73 \mbox{}\ \ \ \ \ \ \ \ dist\textcolor{BrickRed}{[}nodos\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]]}\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0.00}\textcolor{BrickRed}{;} \\
  74 \mbox{}\ \ \ \ \ \ \textcolor{Red}{\}} \\
  75 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  76 \mbox{}\ \ \textcolor{Red}{\}} \\
  77 \mbox{} \\
  78 \mbox{}\ \ \textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{dijkstra}}\textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{const}}\ \textcolor{ForestGreen}{double}\ \textcolor{BrickRed}{\&}maxPath\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}finalPoint\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  79 \mbox{}\ \ \ \ \textbf{\textcolor{Black}{initialize}}\textcolor{BrickRed}{();} \\
  80 \mbox{}\ \ \ \  \\
  81 \mbox{}\ \ \ \ priority$\_$queue\textcolor{BrickRed}{$<$}point\textcolor{BrickRed}{,}\ vector\textcolor{BrickRed}{$<$}point\textcolor{BrickRed}{$>$,}\ heapCompare\ \textcolor{BrickRed}{$>$}\ q\textcolor{BrickRed}{;} \\
  82 \mbox{}\ \ \ \ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{push}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{point}}\textcolor{BrickRed}{(}\textcolor{Purple}{0.0}\textcolor{BrickRed}{,}\ \textcolor{Purple}{0.0}\textcolor{BrickRed}{));} \\
  83 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(!}q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{empty}}\textcolor{BrickRed}{())}\textcolor{Red}{\{} \\
  84 \mbox{}\ \ \ \ \ \ point\ u\ \textcolor{BrickRed}{=}\ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{top}}\textcolor{BrickRed}{();} \\
  85 \mbox{}\ \ \ \ \ \ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{pop}}\textcolor{BrickRed}{();} \\
  86 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Black}{distancia}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{point}}\textcolor{BrickRed}{(}\textcolor{Purple}{0.00}\textcolor{BrickRed}{,}\ \textcolor{Purple}{0.00}\textcolor{BrickRed}{),}\ u\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{+}\ \textbf{\textcolor{Black}{distancia}}\textcolor{BrickRed}{(}u\textcolor{BrickRed}{,}\ finalPoint\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{$<$=}\ maxPath\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  87 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}vecinos\textcolor{BrickRed}{[}u\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  88 \mbox{}\ \ \ \ \ \ \ \ \ \ point\ v\ \textcolor{BrickRed}{=}\ vecinos\textcolor{BrickRed}{[}u\textcolor{BrickRed}{][}i\textcolor{BrickRed}{];} \\
  89 \mbox{}\ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}dist\textcolor{BrickRed}{[}vecinos\textcolor{BrickRed}{[}u\textcolor{BrickRed}{][}i\textcolor{BrickRed}{]]}\ \textcolor{BrickRed}{$>$}\ \textcolor{BrickRed}{(}dist\textcolor{BrickRed}{[}u\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{+}\ \textbf{\textcolor{Black}{distancia}}\textcolor{BrickRed}{(}u\textcolor{BrickRed}{,}v\textcolor{BrickRed}{)))}\textcolor{Red}{\{} \\
  90 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ dist\textcolor{BrickRed}{[}vecinos\textcolor{BrickRed}{[}u\textcolor{BrickRed}{][}i\textcolor{BrickRed}{]]}\ \textcolor{BrickRed}{=}\ dist\textcolor{BrickRed}{[}u\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{+}\ \textbf{\textcolor{Black}{distancia}}\textcolor{BrickRed}{(}u\textcolor{BrickRed}{,}\ v\textcolor{BrickRed}{);} \\
  91 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{push}}\textcolor{BrickRed}{(}v\textcolor{BrickRed}{);} \\
  92 \mbox{}\ \ \ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  93 \mbox{}\ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  94 \mbox{}\ \ \ \ \ \ \textcolor{Red}{\}} \\
  95 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  96 \mbox{}\ \ \textcolor{Red}{\}} \\
  97 \mbox{} \\
  98 \mbox{}\textcolor{Red}{\}}\textcolor{BrickRed}{;} \\
  99 \mbox{} \\
 100 \mbox{} \\
 101 \mbox{} \\
 102 \mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{main}}\textcolor{BrickRed}{()}\textcolor{Red}{\{} \\
 103 \mbox{}\ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{true}}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
 104 \mbox{} \\
 105 \mbox{}\ \ \ \ string\ s\textcolor{BrickRed}{;} \\
 106 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}s\ \textcolor{BrickRed}{=}\ \texttt{\textcolor{Red}{"{}"{}}}\textcolor{BrickRed}{;}\ s\ \textcolor{BrickRed}{==}\ \texttt{\textcolor{Red}{"{}"{}}}\textcolor{BrickRed}{;}\ \textbf{\textcolor{Black}{getline}}\textcolor{BrickRed}{(}cin\textcolor{BrickRed}{,}\ s\textcolor{BrickRed}{));} \\
 107 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}s\ \textcolor{BrickRed}{==}\ \texttt{\textcolor{Red}{"{}*"{}}}\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{break}}\textcolor{BrickRed}{;} \\
 108 \mbox{} \\
 109 \mbox{} \\
 110 \mbox{}\ \ \ \ grafo\ g\textcolor{BrickRed}{;} \\
 111 \mbox{} \\
 112 \mbox{}\ \ \ \ stringstream\ line\textcolor{BrickRed}{;} \\
 113 \mbox{}\ \ \ \ line\ \textcolor{BrickRed}{$<$$<$}\ s\textcolor{BrickRed}{;} \\
 114 \mbox{} \\
 115 \mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ w\textcolor{BrickRed}{,}h\textcolor{BrickRed}{;} \\
 116 \mbox{}\ \ \ \ line\ \textcolor{BrickRed}{$>$$>$}\ w\ \textcolor{BrickRed}{$>$$>$}\ h\textcolor{BrickRed}{;} \\
 117 \mbox{}\ \ \ \ g\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{insert}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{point}}\textcolor{BrickRed}{((}\textcolor{ForestGreen}{double}\textcolor{BrickRed}{)}w\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{double}\textcolor{BrickRed}{)}h\textcolor{BrickRed}{));} \\
 118 \mbox{}\ \ \ \ g\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{insert}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{point}}\textcolor{BrickRed}{(}\textcolor{Purple}{0.00}\textcolor{BrickRed}{,}\ \textcolor{Purple}{0.00}\textcolor{BrickRed}{));} \\
 119 \mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ noPuntos\textcolor{BrickRed}{;} \\
 120 \mbox{}\ \ \ \ cin\ \textcolor{BrickRed}{$>$$>$}\ noPuntos\textcolor{BrickRed}{;} \\
 121 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}noPuntos\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
 122 \mbox{}\ \ \ \ \ \ \textcolor{ForestGreen}{double}\ x\textcolor{BrickRed}{,}y\textcolor{BrickRed}{;} \\
 123 \mbox{}\ \ \ \ \ \ cin\ \textcolor{BrickRed}{$>$$>$}\ x\ \textcolor{BrickRed}{$>$$>$}\ y\textcolor{BrickRed}{;} \\
 124 \mbox{}\ \ \ \ \ \ g\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{insert}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{point}}\textcolor{BrickRed}{(}x\textcolor{BrickRed}{,}y\textcolor{BrickRed}{));} \\
 125 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
 126 \mbox{} \\
 127 \mbox{}\ \  \\
 128 \mbox{}\ \ \ \ \textcolor{ForestGreen}{double}\ maximoCamino\textcolor{BrickRed}{;} \\
 129 \mbox{}\ \ \ \ cin\ \textcolor{BrickRed}{$>$$>$}\ maximoCamino\textcolor{BrickRed}{;} \\
 130 \mbox{} \\
 131 \mbox{}\ \ \ \ g\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{make$\_$vecinos}}\textcolor{BrickRed}{(}maximoCamino\textcolor{BrickRed}{);} \\
 132 \mbox{} \\
 133 \mbox{}\ \ \ \ g\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{dijkstra}}\textcolor{BrickRed}{(}maximoCamino\textcolor{BrickRed}{,}\ \textbf{\textcolor{Black}{point}}\textcolor{BrickRed}{((}\textcolor{ForestGreen}{double}\textcolor{BrickRed}{)}w\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{double}\textcolor{BrickRed}{)}h\textcolor{BrickRed}{));} \\
 134 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}dist\textcolor{BrickRed}{[}\textbf{\textcolor{Black}{point}}\textcolor{BrickRed}{((}\textcolor{ForestGreen}{double}\textcolor{BrickRed}{)}w\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{double}\textcolor{BrickRed}{)}h\textcolor{BrickRed}{)]}\ \textcolor{BrickRed}{$<$=}\ maximoCamino\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
 135 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Black}{printf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}I\ am\ lucky!}}\texttt{\textcolor{CarnationPink}{\textbackslash{}n}}\texttt{\textcolor{Red}{"{}}}\textcolor{BrickRed}{);} \\
 136 \mbox{}\ \ \ \ \textcolor{Red}{\}}\textbf{\textcolor{Blue}{else}}\textcolor{Red}{\{} \\
 137 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Black}{printf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}Boom!}}\texttt{\textcolor{CarnationPink}{\textbackslash{}n}}\texttt{\textcolor{Red}{"{}}}\textcolor{BrickRed}{);} \\
 138 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
 139 \mbox{}\ \ \  \\
 140 \mbox{}\ \ \textcolor{Red}{\}} \\
 141 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
 142 \mbox{}\textcolor{Red}{\}} \\
 143